package class_0922redblacktree;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class RedBlackTree<K,V> {
    //比较器字段： ---可以考虑传递一个比较器对象， 比较器对象优于Comparable中的compareTo实现
    private final Comparator<? super K> comparator;
    public transient int size;
    public Entry<K,V> root;
    //虚拟节点的key, value规定为null.--->至于其三方向指针可以修改
    private static final Entry NIL = new Entry<>(null,null);
    {
        NIL.parent = NIL;
        NIL.left = NIL;
        NIL.right = NIL;
    }

    public RedBlackTree(Comparator<? super K> comparator) {
        root = NIL;
        this.comparator = comparator;
    }

    public RedBlackTree() {
        this(null);
    }
    public V put(K key, V value) throws NullPointerException{
        Comparator<? super K> cpr = comparator;//获得比较器对象
        Entry<K,V> node = new Entry<>(key,value);
        if(cpr != null) {
            // 若比较器不为空, 则优先选择比较器。
            Entry<K,V> p = NIL;
            Entry<K,V> cur = root;
            while(cur != NIL) {
                p = cur;
                // key 与 cur.getKey(); 比较
                int cmp = cpr.compare(key, cur.getKey());
                if(cmp < 0) {
                    //key 小于当前节点
                    cur = cur.left;
                }
                else if(cmp > 0) {
                    cur = cur.right;
                }
                else{
                    // 当前key存在 ,重复key更新值即可
                    return p.setValue(value);
                }
            }
            node.parent = p;
            if(p==NIL){
                root = node;
            }
            else if(comparator.compare(key,p.getKey()) < 0){
                p.left = node;
            }
            else{
                p.right = node;
            }
        }
        else{
            //采取默认比较---则对象必须实现Comparable接口
            if(key==null){
                //非NIL的Entry对象不允许key为空。
                throw new NullPointerException("key is null");
            }
            //检查一下
            @SuppressWarnings("unchecked")
            Comparable<? super K> com = (Comparable<? super K>) key;
            Entry<K,V> p = NIL;
            Entry<K,V> cur = root;
            while(cur != NIL) {
                p = cur;
                int cmp = com.compareTo(key);
                if(cmp < 0) {
                    //key 小于当前节点
                    cur = cur.left;
                }
                else if(cmp > 0) {
                    cur = cur.right;
                }
                else{
                    // 当前key存在 ,重复key更新值即可
                    return p.setValue(value);
                }
            }
            node.parent = p;
            if(p==NIL){
                root = node;
            }
            else if(comparator.compare(key,p.getKey()) < 0){
                p.left = node;
            }
            else{
                p.right = node;
            }
        }
        node.left = NIL;
        node.right = NIL;
        node.color = Color.RED;
        fixAfterInsert(node);
        return value;
    }
    private static <K,V>void leftRotate(RedBlackTree<K,V> T, Entry<K,V> entry){
        Entry<K,V> tmp = entry.right;
        entry.right = tmp.left;
        if(tmp.left!=RedBlackTree.NIL){

        }
    }
    private static <K,V>void rightRotate(RedBlackTree<K,V> T, Entry<K,V> entry){

    }
    private static<K,V> void fixAfterInsert(Entry<K,V> node) {
        return ;
    }

    //枚举---红黑色：描述红黑树的性质一。
    enum Color{
        BLACK,RED;
    }
    static final class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> left;
        Entry<K, V> right;
        Entry<K, V> parent;
        Color color = Color.BLACK;

        Entry(K key, V value) {
            this(key, value, null);
        }

        Entry(K key, V value, Entry<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        public K getKey() {
            return key;
        }
        public V getValue() {
            return value;
        }
        public V setValue(V value) {
            V old = this.value;
            this.value = value;
            return old;
        }

        public String toString() {
            return key + "=" + value;
        }
    }
}
